﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习十月份
{
    public class Solution24
    {
        public ListNode SwapPairs1(ListNode head)
        {
            if (head == null || head.next == null) return head;

            ListNode next = head.next;

            head.next = SwapPairs(next.next);
            next.next = head;

            return next;
        }

        public ListNode SwapPairs2(ListNode head)//递归
        {
            if (head == null || head.next == null)
            {
                return head;
            }

            ListNode newHead = head.next;

            head.next = SwapPairs(newHead.next);

            newHead.next = head;
            return newHead;
        }

        public ListNode SwapPairs(ListNode head)//迭代
        {
            ListNode dummy = new ListNode();
            dummy.next = head;

            ListNode next = dummy;
            ListNode pre = dummy;
            ListNode cur = dummy;

            while (pre.next != null && pre.next.next != null)
            {
                cur = pre.next;
                next = cur.next;
                //交换
                pre.next = next;
                cur.next = next.next;
                next.next = cur;

                //更新
                pre = cur;
            }

            return dummy.next;
        }
    }
}